package com.peng.tree.foreach;

import com.peng.tree.Node;

import java.util.Stack;

/**
 * 对树结构的深度优先遍历
 * 非递归版本
 */
public class DeepForEach_NO_Recursion {

    /**
     * 头左右
     *
     * @param head
     */
    public static void pre(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.add(head);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.value);
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }

    }

    public static void mid(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while (!stack.empty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                Node pop = stack.pop();
                System.out.println(pop.value);
                cur = pop.right;
            }
        }
    }

    /**
     * 先序是头左右，  只需要改变压入顺序可以很轻易完成头右左， 而把这个行为先不打印，放入另外一个栈中，再依次输出，得到的就是左右头
     * 后序是左右头
     *
     * @param head
     */
    public static void post(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        Stack<Node> res = new Stack<>();
        stack.add(head);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            res.push(cur);
            if (cur.left != null) {
                stack.push(cur.left);
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
        }

        while (!res.empty()) {
            System.out.println(res.pop().value);
        }
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);

        node.left = node2;
        node.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;
        /*
                   1
             2              3
           4   5         6     7
         8   9

         */
        System.out.println("=========先序==========");
        DeepForEach_Recursion.pre(node);
        System.out.println("===================");
        pre(node);

        System.out.println("=========后序==========");

        DeepForEach_Recursion.post(node);
        System.out.println("===================");
        post(node);

        System.out.println("=========中序==========");

        DeepForEach_Recursion.mid(node);
        System.out.println("===================");
        mid(node);


    }
}
